玩具蛇
题目 玩具蛇
思路分析
首先要做一遍全排列 问题是 怎么判断某个排列是否合法
存在图里面 然后遍历图 对图的每个位置往4方向拓展 看有没有相邻的数 如果没有则一定不合法？貌似可行 但有些太暴力了吧……
结果半天不出来
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<int> a={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
int m[4][4];
bool st[4][4];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=3 && y>=0 && y<=3;
}
void dfs(int x, int y, bool& flag) {
if (!flag)
return;
int cnt = 0;
for (int i=0;i<4;i++) {
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx, ny)) {
if(abs(m[nx][ny]-m[x][y])!=1)
cnt++;
if(abs(m[nx][ny]-m[x][y])==1 && !st[nx][ny]){
st[nx][ny] = true;
dfs(nx, ny, flag);
}
}
}
if(cnt == 4)
flag=false;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
long long cnt=0;
do{
memset(st,false,sizeof st);
// m[0][0]=a[0],m[0][1]=a[1],m[0][2]=a[2],m[0][3]=a[3];
// m[1][0]=a[4],m[1][1]=a[5],m[1][2]=a[6],m[1][3]=a[7];
// m[2][0]=a[8],m[2][1]=a[9],m[2][2]=a[10],m[2][3]=a[11];
// m[3][0]=a[12],m[3][1]=a[13],m[3][2]=a[14],m[3][3]=a[15];
for(int i=0;i<16;i++){
m[i/4][i%4]=a[i];
}
bool flag = true;
st[0][0] = true;
dfs(0,0,flag);
if(flag)
cnt++;
}while(next_permutation(a.begin(),a.end()));
cout<<cnt;
return 0;
}
等等看吧 先写后面的
不行 几个小时都算不出来 得换个角度
从八皇后的角度来看 每个位置能不能放置
枚举每个位置 以它为起点 开始放蛇 若最后放满16个格子 就是一种合法方案
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int cnt;
bool st[4][4];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=3 && y>=0 && y<=3 && !st[x][y];
}
void dfs(int step,int x,int y){
if(step==16){
cnt++;
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny)){
st[nx][ny]=true;
dfs(step+1,nx,ny);
st[nx][ny]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=0;i<4;i++){ //对4x4的格子 枚举玩具蛇第一个步放置的所有可能
for(int j=0;j<4;j++){
st[i][j]=true;
dfs(1,i,j);
st[i][j]=false;
}
}
cout<<cnt;
return 0;
}
代码实现
💬 评论